package algorithm.List.Queue;

import algorithm.linkedList.ListNode;

import java.util.Stack;

/**
 * 用数组和链表两种方式实现队列
 */
public class MyQueue {

    //这里使用单向链表
    //双向链表也能实现
    public static class MyQueueLinkedList{
        private ListNode head;
        private ListNode tail;

        public MyQueueLinkedList(int val){
            head=new ListNode(val);
            tail=head.next;
        }
        public void push(int val){
            tail=new ListNode(val);
            tail=tail.next;
        }
        public int pop(){
            ListNode next=head.next;
            int num=head.val;
            head.next=null;
            head=next;
            return num;
        }
        public boolean isEmpty(){
            //head和tail指向同一位置的话就是空的
            //左闭右开
            return head==tail;
        }
        public int size(){
            ListNode cur=head;
            int size=0;
            while(cur!=tail){
                size++;
                cur=cur.next;
            }
            return size;
        }
    }

    //普通数组实现的队列
    public static class MyQueueArray{
        private int[] array;
        private int l,r;
        private int capacity;

        public MyQueueArray(int n){
            array=new int[n];
            capacity=n;
            l=0;
            r=0;
        }
        public boolean isEmpty(){
            return l==r;
        }
        public void push(int val){
            if(r>=capacity) return;
            array[r++]=val;
        }
        public int head(){
            if(isEmpty()) return -1;
            return array[l];
        }
        public int tail(){
            if(isEmpty()) return -1;
            return array[r-1];
        }
        public int pop(){
            if(isEmpty()) return -1;
            return array[l++];
        }
        public int size(){
            return r-l;
        }

    }

    /**
     * 使用Java自带的stack模拟queue
     */
    public static class MyQueueUsingStack{
        public Stack<Integer> in;
        public Stack<Integer> out;

        public MyQueueUsingStack(){
            in=new Stack<Integer>();
            out=new Stack<Integer>();
        }
        private void inToOut(){
            if(out.empty()){
                while(!in.empty()){
                    out.push(in.pop());
                }
            }
        }
        public boolean empty(){
            return out.empty()&&in.empty();
        }
        public void push(int val){
            in.push(val);
            inToOut();
        }
        public int pop(){
            inToOut();
            return out.pop();
        }
        public int peek(){
            inToOut();
            return out.peek();
        }
    }

}
